#include <stdio.h>
#include <stdlib.h>

// 二叉树 库文件：为了简化 .h 和 .c 合并到一个文件

struct Student{
    int id;
    char* name;
    int score;
};

// 定义节点
struct TreeNode{
    int data; //也可以是另一个 结构体类型
    //Student *data;
    struct TreeNode *left; //注意要加前缀
    struct TreeNode *right;
};

// 中序遍历树
void inOrder(struct TreeNode *p){
    if(p){
        inOrder(p->left);
        printf("%d > ", p->data);
        inOrder(p->right);
    }
}

//释放二叉树
void freeTree(struct TreeNode* p){
    if(p){
        freeTree(p->left);
        freeTree(p->right);
        free(p);
    }
}

//打印二叉树：类似 linux 命令 tree
void printTree(struct TreeNode* root, int depth, char* prefix) {
    if (root == NULL) return;
    
    // 打印当前节点前的基础缩进
    for (int i = 1; i < depth; i++) {
        //printf("%s", (i == depth-1) ? "│  " : "   ");
        printf("%s", "│  ");
    }
    // 打印当前节点的值
    printf("%s%d\n", prefix, root->data);

    // 递归打印子节点
    if (root->left || root->right) {
        printTree(root->left, depth + 1, "├──L:");
        printTree(root->right, depth + 1, "└──R:");
    }
}

// 递归式：给树 root 插入元素 val
struct TreeNode* insert(struct TreeNode *root, int val){
    if(root==NULL){
        struct TreeNode *p = (struct TreeNode*) malloc( sizeof(struct TreeNode) );
        p->data= val;
        p->left = NULL;
        p->right=NULL;
        // printf(">> Insert value %d to tree\n", val);
        return p;
    }
    if( val < root->data){
        // printf(">> Insert value %d to tree left\n", val);
        root->left = insert(root->left, val); //如果值小，往左插入
    }else if( val > root->data){
        // printf(">> Insert value %d to tree right\n", val);
        root->right = insert(root->right, val); //如果值大，往右插入
    }
    return root;
}

// 迭代式：给树 root 插入元素 val
struct TreeNode* insert2(struct TreeNode *root, int val){
    struct TreeNode* p = (struct TreeNode*) malloc( sizeof(struct TreeNode) );
    p->data= val;
    p->left = NULL;
    p->right=NULL;

    if(root==NULL){
        return p;
    }

    //找到将会添加新节点的节点，作为父节点：叶子节点
    struct TreeNode *parent=NULL, *curr=root; //根节点
    while( curr!=NULL){
        parent = curr;
        if(val < curr->data){
            curr = curr->left;
        }else if(val > curr->data){
            curr = curr->right;
        }else{
            return root; //找到值相等，啥也不干，直接返回 root 树
        } // 如果找到指针为空，则其父节点可以插入值
    }

    // 如果小于根，插入左侧
    if( val < parent->data){
        parent->left = p;
    }else{ //如果大于根，插入右侧
        parent->right = p;
    }
    return root;
}



// ################ search a key

/*
* 递归：在树root中查找值key是否存在
* 把返回值和 NULL 做比较，就是布尔值 true / false
Time complexity: O(h), where h is the height of the BST.
Auxiliary Space: O(h) This is because of the space needed to store the recursion stack.
*/
struct TreeNode* search(struct TreeNode* root, int key){
    // Base Cases: root is null or key is present at root
    if(root == NULL || root->data == key){
        return root;
    }
    
    if(key < root->data){
        return search(root->left, key);
    }else{
        return search(root->right, key);
    }
}


/*
* 迭代法：在树root中查找值key是否存在。比递归需要更少的内存空间
* 把返回值和 NULL 做比较，就是布尔值 true / false；也可以直接返回1或0
Time Complexity: O(h), where h is the height of the BST.
Auxiliary Space: O(1)
*/
struct TreeNode* search2(struct TreeNode* root, int key){
    struct TreeNode* curr=root;
    while(curr!=NULL){
        if(curr->data == key){
            return root;
        }
        if(key < curr->data){
            curr=curr->left;
        }else{
            curr=curr->right;
        }
    }

    return curr;
}




// ################ delete a key

/*
desc: 找继任节点：整个树比该节点大的那个节点。
example: 如 10 50 60 要删除50，那么该函数返回其继任 60
Aim: 用于和被删除节点的值互换。
* Note that it is not a generic inorder successor function. 
* It mainly works when the right child is not empty, which is  the case we need in BST delete.
*/
struct TreeNode* getSuccessor(struct TreeNode* curr) {
    curr = curr->right;
    while (curr != NULL && curr->left != NULL)
        curr = curr->left;
    return curr;
}


/*
删除节点
分三种情况：
1. 叶子节点：直接删
2. 只有一个子节点的父节点：复制子节点的值到该节点，删除子节点。
* Copy the child to the node and delete the child. 
3. 有两个叶子节点的父节点: 很复杂，还需要保证最后剩下的树还是BST树
* The trick is to find the inorder successor of the node. Copy contents of the inorder successor to the node, and delete the inorder successor.
技巧是：找到该节点的 中序 继承者，复制其继承者的值到该节点，然后删除 继承者节点。
* Note: Inorder predecessor can also be used.
会用到 其 中序前任
#
Time Complexity: O(h), where h is the height of the BST. 
Auxiliary Space: O(h).
当有2个子节点时，该函数遍历2次。还可以优化。
*/
struct TreeNode* deleteNode(struct TreeNode* root, int key){
    // Base case
    if (root == NULL)
        return root;

    if(key < root->data){
        root->left = deleteNode(root->left, key);
    }else if(key > root->data){
        root->right = deleteNode(root->right, key);
    }else{
        //如果该节点的值==key
        //1. 没有子节点: 
        /*已被包含到情形2: left为空，则返回right，无论right是不是null
        if(root->left==NULL && root->right==NULL){
            free(root);
            return NULL;
        }*/
        //2. 只有一个节点
        if(root->left == NULL){
            struct TreeNode* temp = root->right;
            free(root);
            return temp;
        }
        if(root->right == NULL){
            struct TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        //3. 同时有两个子节点
        //找到下一个节点
        struct TreeNode* next = getSuccessor(root);
        //获取其 下一个节点的值
        root->data= next->data;
        //右侧删除该节点
        root->right = deleteNode(root->right, next->data);
    }

    return root;
}

/*
优化 递归删除：左右子节点都存在，怎么减少一次遍历？获取 中序下一个元素的父节点
#
Time Complexity: O(h), where h is the height of the BST. 
Auxiliary Space: O(h).
*/
struct TreeNode* deleteNode_B(struct TreeNode* root, int key){
    // Base case
    if (root == NULL)
        return root;

    if(key < root->data){
        root->left = deleteNode_B(root->left, key);
    }else if(key > root->data){
        root->right = deleteNode_B(root->right, key);
    }else{
        //如果该节点的值==key
        //1. 没有子节点: 
        /*已被包含到情形2: left为空，则返回right，无论right是不是null
        if(root->left==NULL && root->right==NULL){
            free(root);
            return NULL;
        }*/
        //2. 只有一个节点
        if(root->left == NULL){
            struct TreeNode* temp = root->right;
            free(root);
            return temp;
        }
        if(root->right == NULL){
            struct TreeNode* temp = root->left;
            free(root);
            return temp;
        }

        //3. 同时有两个子节点(优化：只需要一次遍历)
        
        //找到下一个节点，记录其夫节点
        // Node with two children: Get the inorder successor (smallest in the right subtree).
        // Also find parent of the successor
        struct TreeNode* succParent = root;
        struct TreeNode* succ = root->right; //右树中的最小值
        while (succ->left != NULL) {
            succParent = succ;
            succ = succ->left;
        }

        //获取其 下一个节点的值
        // Copy the inorder successor's content to this node
        root->data= succ->data;

        // Delete the inorder successor
        if (succParent->left == succ) {
            succParent->left = succ->right;
        } else {
            /*
            什么时候执行这一句？最小值不在左侧，就是要删除的元素的right 没有left
            比如: 5 8 7 9 /  del 8
            5
             \
              8  del this node, the smallest is its right, which have no left node.
              /\
             7  9
            after delete:
            5
             \
              9
              /
             7
            */
            printf(">> succParent->right = succ->right; \n");
            succParent->right = succ->right;
        }
        //释放该节点的next
        free(succ);
    }

    return root;
}


/*
删除元素，迭代法
#
Time Complexity : O(h) where h is height of the BST
Auxiliary Space: O(1)
*/
struct TreeNode* deleteNodeIterative(struct TreeNode* root, int key){
    printf("\t>> delete key iterative\n");
    struct TreeNode* curr = root;
    struct TreeNode* prev = NULL; //要删除节点的 父节点

    //找到要删除的元素
    while(curr!=NULL && curr->data != key){
        prev=curr;
        if(key < curr->data){
            curr=curr->left;
        //}else if(key > curr->data){
        }else{
            curr=curr->right;
        }
    }
    //key not found
    if(curr==NULL){
        return root;
    }else{
        printf("\t>>找到元素: %d，执行删除ing\n", curr->data);
    }

    // check if the node has at most 1 child
    if(curr->left ==NULL || curr->right==NULL){
        struct TreeNode* newCurr;
        if(curr->left == NULL){
            newCurr = curr->right;
        }else{
            newCurr = curr->left;
        }

        // 如果要删除的是root
        if(prev == NULL){
            return newCurr;
        }
        // 否则，父元素指向新当前，删除当前
        //if(curr->data == prev->left->data){
        if(curr == prev->left){ //这样怎么比较的？
            prev->left = newCurr;
        }else{
            prev->right = newCurr;
        }
        //释放当前
        free(curr);
    }else{
        //要删除的节点有2个子节点
        //先获取右侧的最小值，及其父节点
        struct TreeNode* nextParent=NULL;
        struct TreeNode* next=curr->right; //curr的下一个节点，其值给curr，然后释放内存
        while(next->left != NULL){
            nextParent = next;
            next = next->left;
        }

        //
        if(nextParent != NULL){
            //表示要删除的节点right node 有左侧值
            nextParent->left = next->right;
        }else{
            //其right没有左侧值
            /*
            5
             \
              8 delete this, nextP=NULL, next=right;
              /\
              7 9
            */
           curr->right = next->right;
        }

        // next 值给 curr
        curr->data = next->data;

        //释放 next
        free(next);
    }
    return root;
}

